/**
 * Using Stack is the obvious way to traverse tree without recursion.
 * Below is an algorithm for traversing binary tree using stack.
 * See this for step wise execution of the algorithm
 * 1) Create an empty stack S.
 * 2) Initialize current node as root
 * 3) Push the current node to S and set current = current->left until current is NULL
 * 4) If current is NULL and stack is not empty then
 *  a) Pop the top item from stack.
 *  b) Print the popped item, set current = popped_item->right
 *  c) Go to step 3.
 * 5) If current is NULL and stack is empty then we are done.
 * 
 **/
#include <iostream>
#include <stack>
using namespace std;

struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
    Node (int data)
    {
        this->data = data;
        left = right = NULL;
    }
};

/* Iterative function for inorder tree traversal */
void inOrder(struct Node *root)
{
    stack<Node *> s;
    Node *curr = root;

    while(curr != NULL || s.empty() == false)
    {
        /* Reach the left most Node of the curr node */
        while (curr != NULL)
        {
            /* place pointer to a tree node on the stack before traversing the node's left subtree */
            s.push(curr);
            curr = curr->left;
        }

        /* Current must be NULL at this point */
        curr = s.top();
        s.pop();

        cout << curr->data << " ";
        /* we have visited the node and its left subtree. Now, it's right subtree's turn */
        curr = curr->right;
    } /* end of while */
}

int main()
{
    /* Constructed binary tree is 
              1 
            /   \ 
          2      3 
        /  \ 
      4     5 
    */
   struct Node *root = new Node(1); 
    root->left        = new Node(2); 
    root->right       = new Node(3); 
    root->left->left  = new Node(4); 
    root->left->right = new Node(5); 
  
    inOrder(root); 
    return 0; 
}